package com.zhugang.week12;

/**
 * @program algorithms
 * @description: ProductExceptSelf3
 * @author: chanzhugang
 * @create: 2022/09/08 22:45
 */
public class ProductExceptSelf3 {


    /**
     * 238 除自身外数组的乘积
     * 空间复杂度更低，只在一个数组上操作
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf3(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        int leftProduct = 1;
        for (int i = 0; i < n; i++) {
            // 不包含第i个元素
            result[i] = leftProduct;
            leftProduct *= nums[i];
        }

        int rightProduct = 1;

        for (int i = n - 1; i >= 0; i--) {
            // 前面i个元素乘积 * 后面元素乘积
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        return result;
    }
}